__author__ = 'soso_fy'

# coding:utf-8

import random
import math

# 这里用python实现一个简单的遗传算法
# 计算 f（x）在[0，255]整数范围内的最大值
# 个体编码 00000000~11111111


# 待求值的函数,这里先简单写个
def function(x):
    return math.sin(x) + math.sin(2*x)/2 + math.sin(3*x)/3 + math.sin(4*x)/4

# 随机生成一个个体
def genRandomUnit():
    return random.randint(0, 255)

# 获取当代的最优解
def getBestSolution(currentGeneration):
    result = -99999999
    u = ''
    for unit in currentGeneration:
        if function(int(unit, 2)) > result:
            result = function(int(unit, 2))
            u = unit
    print('x = ' + str(int(u, 2)) + ' f(x) = ' + str(result))
    return u

# 随机创建指定数量的第一代样本
def genFirstGeneration(count):
    list = []
    for index in range(count):
        unit = bin(genRandomUnit())
        while list.count(unit) > 0:
            unit = bin(genRandomUnit())
        list.append(unit)
    #print('first generation')
    #print(list)
    return list

# 从当前代选择进入下一代的个体
def chooseNextGeneration(currentGeneration):
    gotoNext = []
    total = 0
    for unit in currentGeneration:
        total += function(int(unit, 2))
    for unit in currentGeneration:
        p = function(int(unit, 2)) / total
        if random.random() <= p:
            gotoNext.append(unit)
            currentGeneration.remove(unit)
    #print('choose generation')
    #print(gotoNext)
    return gotoNext

# 交叉产生下一代
def crossNextGeneration(currentGeneration):
    p = 0.5  # 交叉概率为50%
    crossList = [] # 需要交叉的个体
    for unit in currentGeneration:
        if random.random() <= p:
            crossList.append(unit)
            currentGeneration.remove(unit)
    # crossList数量为奇数时，随机删除一个
    if len(crossList) % 2 != 0:
        index = random.randint(0, len(crossList) - 1)
        currentGeneration.append(crossList[index])
        del crossList[index]
    #print('cross generation')
    #print(crossList)
    # 随机配对交叉
    crossResult = []
    count = int(len(crossList) / 2)
    for index in range(count):
        pairIndex = random.randint(1, len(crossList) - 1)
        unitA = crossList[0]
        unitB = crossList[pairIndex]
        crossList.remove(unitA)
        crossList.remove(unitB)
        A, B = cross(unitA, unitB)
        crossResult.append(A)
        crossResult.append(B)
    return crossResult

# 对当前代变异
def variationGeneration(currentGeneration):
    result = []
    for unit in currentGeneration:
        result.append(variation(unit))
    return result

# 个体交叉
def cross(unitA, unitB):
    unitA = unitA[2:].rjust(8, '0')
    unitB = unitB[2:].rjust(8, '0')
    #print(unitA + ' ' + unitB)
    startPos = random.randint(0, 7)
    endPos = random.randint(0, 7)
    if startPos > endPos:
        tmp = startPos
        startPos = endPos
        endPos = tmp
    partA = unitA[startPos:endPos]
    partB = unitB[startPos:endPos]
    unitA = '0b' + unitA[0:startPos] + partB + unitA[endPos:]
    unitB = '0b' + unitB[0:startPos] + partA + unitB[endPos:]
    #print(unitA + ' ' + unitB)
    return unitA, unitB

# 个体变异
def variation(unit):
    unit = unit[2:].rjust(8, '0')
    index = random.randint(0, 7)
    #print(unit)
    if unit[index] == '1':
        unit = unit[0:index] + '0' + unit[index+1:]
    else:
        unit = unit[0:index] + '1' + unit[index+1:]
    #print(unit)
    return '0b' + unit

list = genFirstGeneration(10)
# 迭代100次
for t in range(100):
    print(list)
    # 生成下一代种群
    bestUnit = getBestSolution(list)
    list.remove(bestUnit)
    choosList = chooseNextGeneration(list)
    crossList = crossNextGeneration(list)
    variationList = variationGeneration(list)
    # 下一代
    list = []
    list.append(bestUnit)
    list.extend(choosList)
    list.extend(crossList)
    list.extend(variationList)